The present invention relates generally to network switches and, more particularly, to an polling mechanism for use in a network switch having a number of interfaces.
Asynchronous Transfer Mode (ATM) or xe2x80x9ccell switchingxe2x80x9d is a method of transmitting digital information wherein the information is broken into equal sized units called xe2x80x9ccells.xe2x80x9d The individual cells of information are transmitted from a source node to a destination node through a xe2x80x9cconnectionxe2x80x9d. A connection is a pathway through a digital network. A digital network is constructed of digital switch nodes coupled together by digital communication links. xe2x80x9cPacketxe2x80x9d switching is a similar technology, however, in packet switching networks, variable length packets (instead of fixed length cells) are transmitted between nodes.
Each cell or packet originates at a source node and is transmitted across the communication links. The communication links carry the cells or packets of information between the digital switch nodes along the connection pathway. The digital switch nodes route the cells or packets from incoming communication links to outgoing communication links and finally to a destination node. Each digital switch node can be connected to several communication links, each of which may carry several different connections simultaneously.
Thus, packet-switched and cell-switched networks use switch nodes to provide a shared transmission path for a multiplicity of ports, thereby reducing the overall cost and complexity of the ports and the network. A port may be coupled to a communication link such as an OC3 line for communicating to another switch node. Alternatively, a port may be coupled to an endpoint of a network such as customer premise equipment (CPEs).
FIG. 1 illustrates such an exemplary digital communications network 100. The network 100 illustrated in FIG. 1 is a cell-switched digital communication network, however, the same principles apply for a packet-switched digital communication network. The digital network 100 is constructed of digital switch nodes that are capable of building virtual circuits for routing cells. Switch nodes 120 and 130 serve as the backbone for a broadband digital Wide Area Network (WAN) 110. Switch nodes 140 and 150 couple smaller narrowband digital communication links to the broadband digital network.
Each digital switch node 120 and 130 is coupled to one or more broadband digital communication links (e.g., E3 lines, T3 lines, OC3 lines, OC12 lines, etc.). The digital switch nodes 120 and 130 are also coupled to digital switch nodes 140 and 150 using broadband digital communication links.
Each digital switch node 140 and 150 in FIG. 1 is used to couple slower digital communication links to the broadband digital communication network 10. The slower communication links may couple various CPE 160 and/or other networks (e.g., frame relay network 170) to these switches. The CPE 160 may consist of any type of digital communication equipment such a Private Branch Exchange (PBX) or a packet router.
Each digital switch 120 and 130 includes one or more port modules. The port modules in each digital switch 120 and 130 can be used to directly connect a digital switch (e.g., digital switch 120) to any customer premise equipment (CPE) 180 that uses asynchronous transfer mode (ATM) communications and supports the proper interface. Such a connection comprises a user to network interface (UNI). The port modules may also support an interface which allows the digital switches 120 and 130 to be connected together (or to other networks, e.g., ATM network 190) via one or more high speed digital communication links. Where a connection is made to another network, the interface comprises a network to network interface (NNI).
FIG. 2 shows a prior switch node 200 (which may resemble switch nodes 120 and/or 130, etc. of FIG. 1) in more detail. Switch node 200 comprises switch module 205 and port modules 210, 215, 220 and 225. Switch module 205 functionally operates as an Nxc3x97N switching fabric having N inputs and N outputs. Therefore, for the example of N=4, switch module 205 is connected to port module 210 via input line 211 and output line 214, to port module 215 via input line 216 and output line 219, to port module 220 via input line 221 and output line 224, and to port module 225 via input line 226 and output line 229.
Port modules 210, 215, 220 and 225 use switch module 205 as a common interconnect for switching data packets (e.g., cells) between one another. The throughput of a switch module output is limited to the throughput of an output line, which typically results in only one packet being switched per output per transaction or xe2x80x9cconnectionxe2x80x9d cycle of switch module 200. Therefore, output or xe2x80x9cportxe2x80x9d contention arises when multiple port modules attempt to simultaneously transmit packets to the same destination port. Because only one packet may be switched to the destination port per connection cycle, the other packets are xe2x80x9cblocked,xe2x80x9d and data loss can occur.
Packet buffering is typically performed to prevent the loss of blocked packets. For example, each of the port modules of switch node 200 includes input buffers to prevent packet loss due to contention for the same destination port module. Input buffers 212, 217, 222 and 227 are shown as first in first out buffers (FIFOs) and store all packets that are to be switched in a first-in-first-out manner, regardless of their destination port. Switch node 200 is said to use xe2x80x9cinput bufferingxe2x80x9d because packets are buffered by the port modules before they enter the switching fabric of switch module 205.
Input buffering allows switch module 205 to operate at the input line speed, which reduces the complexity and cost of switch module 205; however, the throughput of the switch node 200 may be significantly reduced if port contention occurs. When a packet or cell at the head of a FIFO must wait for transmission, all subsequent packets in the FIFO must also wait even though their destination ports may be available during the present connection cycle. This phenomenon is called xe2x80x9chead-of-line blocking.xe2x80x9d
An alternative switch node architecture uses output buffering to provide improved performance relative to input buffered switch nodes. FIG. 3 shows a prior switch node 300 that uses output buffering and comprises switch module 305 and port modules 310, 315, 320 and 325. Switch module 305 functionally operates as an Nxc3x97N switch matrix. Therefore, for the example of N=4, switch module 305 is connected to port module 310 via input line 311 and output line 314, to port module 315 via input line 316 and output line 319, to port module 320 via input line 321 and output line 324, and to port module 325 via input line 326 and output line 329. To guard against data loss due to output contention, switch module 305 includes output buffers 312, 317, 322 and 327 associated with each of the port modules. Output buffers 312, 317, 322 and 327 are shown as FIFOs, but they may be implemented using a shared memory architecture.
Output buffering eliminates the head-of-line blocking effect of input buffered switch nodes. The primary drawback of an output buffered switch node is that the switch module (e.g., switch module 305) must be operated N times faster than the input line speed, which significantly increases the complexity and cost of the switch module when compared to switch modules of an input buffered switch node. For example, output buffering according to conventional schemes typically requires that output buffers be placed on the switch module because each output line only allows one packet to be passed to a port module per connection cycle wherein up to Nxe2x88x921 packets may be received for transfer per connection cycle. The output buffers must operate at the speed of the switch module, and memory costs are therefore significantly increased when compared to the memory costs for input buffering schemes.
In one embodiment, the present invention provides a switch node having arbiter logic configured to gather global information regarding switching requests within the switch node and to control switching of one or more packets through the switch node. The arbiter logic may include a bus snooping interface configured to detect the switching requests within the switch node. The bus snooping interface includes a plurality of switching request destination registers configured to store switching request destination information from the detected switching requests. In addition, the arbiter logic includes a packet switching request array configured to transmit a next switching request within the switch node according to prior switching request destination information stored in the switching request destination registers. The switching of the one or more packets may be through a cross-point switch matrix in the switch node.
In a further embodiment, the present invention involves polling a first of a plurality of port modules of a switch node for a switching request; and transmitting the switching request from the first port module, the switching request being for a destination port module selected according to global information regarding previous switching requests of one or more of the plurality of port modules. The switching request from the first port module may be granted if the destination port module has an available channel to accept a packet associated with the switching request from the first port module. In one embodiment, transmitting the switching request from the first port module may be accomplished by selecting a first of a plurality of enqueued switching requests if the global information regarding previous switching requests indicates that a channel of a destination port module associated with the first enqueued switching request is available to accept a packet associated with the first enqueued switching request, otherwise selecting another of the plurality of enqueued switching requests.
In yet a further embodiment of the present invention, switching requests of a plurality of port modules are monitored for a first of the plurality of port modules. Then, a first destination port module is selected if the monitored switching requests indicate that a maximum number of output channels for the first destination port module have not already been requested, otherwise a next destination port module is selected. The monitoring may be performed at the first port module.
In another embodiment of the present invention, a switch node includes an arbiter coupled to a plurality of input buffers and further coupled to a plurality of destination port modules via a polling bus. The arbiter is configured to detect switching transactions made by the destination port modules and to selectively transmit a packet stored in one of the input buffers to one of the destination port modules having an unrequested channel, as determined according to the detected switching transactions.
In still a further embodiment, the present invention provides an arbiter coupled to a plurality of input buffers and a polling bus. The arbiter is configured to monitor switching activity by a plurality of port modules coupled to the polling bus to determine which of the port modules have at least one available transmission channel through an asymmetric switch module. The arbiter is further configured to send a packet to the asymmetric switch module from one of the input buffers only if a destination port module of the packet has at least one available transmission channel.
Other features and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description which follows below.